package _05_stack.my_implements.exerc;

import _05_stack.my_implements.LinkedListStack;
import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/7 - 12:46
 * 将中缀转后缀（逆波表达式兰）
 */
public class InfixToSuffixTest {
    @Test
    public void test() {
//        String str = "a+b*c-b";
//        String str = "a+b*c-b*d*e+h";
        String str = "0+1*2-3*4*5+6"; // 012*+34*5*-60   =   -52
        String s = infixToSuffix(str);
        System.out.println(s);
    }

    /**
     * 带括号测试
     */
    @Test
    public void test2() {
        String str = "a+b*d+(e+f)"; // abd*+ef++
        System.out.println(infixToSuffix(str));
    }

    /*
        a+b*c      abc*+

        a+b*c-b    abc*+b-
     */
    String infixToSuffix(String str) {
        StringBuffer buf = new StringBuffer();
        // 越往栈顶，运算符优先级越高，因为只有比栈顶高的运算符才会压栈，否则都是弹栈
        LinkedListStack<Character> stack = new LinkedListStack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            switch (c) {
                case '+', '-', '*', '/' -> {
                    if (stack.isEmpty()) {
                        stack.push(c);
                    } else {
                        /*
                        如果当前的运算符c优先级高于栈顶的运算符，则该运算符c继续压栈
                        否则，弹出栈中所有比c小或等于的运算符，再将c压栈
                     */
                        if (getPriority(c) > getPriority(stack.peek())) {
                            stack.push(c);
                        } else {
                            while (!stack.isEmpty() && getPriority(c) <= getPriority(stack.peek())) {
                                buf.append(stack.pop());
                            }
                            stack.push(c);
                        }
                    }
                }
                case '(' -> stack.push(c);
                case ')' -> {
                    while (stack.peek() != '(') {
                        buf.append(stack.pop());
                    }
                    // 将 ( 弹出
                    stack.pop();
                }
                default -> {
                    // 如果是数字，直接压栈
                    buf.append(c);
                }
            }
        }
        while (!stack.isEmpty()) {
            buf.append(stack.pop());
        }
        return buf.toString();
    }

    /**
     * 获取运算符优先级
     *
     * @param c
     * @return 数字越大，优先级越高
     */
    int getPriority(char c) {
        return switch (c) {
            case '+', '-' -> 1;
            case '*', '/' -> 2;
            case '(' -> 0;
            default -> throw new IllegalArgumentException();
        };
    }
}
